package 排序;

import java.util.Arrays;

/**
 * Created by Administrator on 2017/8/25.
 */
public class MyHeapSort {
    public static void main(String[] args) {
        int[] arr = new int[]{3,5,3,0,8,6,1,5,8,6,2,4,9,4,7,0,1,8,9,7,3,1,2,5,9,7,4,0,2};
        insert_sort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void insert_sort(int[] arr){
        //第一步：创建大根堆
        int maxIndex=arr.length-1; //最大索引
        int startIndex=(maxIndex-1)>>1; //从第一个非叶子节点开始整理堆(因为叶子节点已经默认为一个合格的大根堆了)
        for(int i=startIndex;i>=0;i--){ //一直整理到堆顶端
            max_heap_adjust(arr,i,maxIndex); //从非叶子节点i开始，将其整理为最大堆
        }
        //第二步：将大根堆堆定元素和末尾元素交换位置后(最大元素放到最大索引处)，再整理换上去的末尾元素符合大根堆特性
        for(int j=maxIndex;j>0;j--){
            swap(arr,0,j); //和堆顶元素交换
            max_heap_adjust(arr,0,j-1);
        }
    }

    /**
     * @param arr     原始数组
     * @param index   有字节点的索引
     * @param maxIndex  子节点的正常最大索引
     */
    private static void max_heap_adjust(int[] arr, int index, int maxIndex) {
        int left= (index<<1) + 1; //左叶子节点 (特别易错：<<必须要加括号，因为<<优先级比+低)
        int right= left+1; //右叶子节点

        //排除意外情况
        if(left>maxIndex) return;

        //默认左叶子节点为两个叶子节点或单个叶子节点的最大值
        int max=left;
        //若存在右叶子节点，和左叶子节点比较，得到较大者
        if(right<=maxIndex && arr[left]<arr[right]){
            max=right;
        }

        //若叶子节点大于父节点，交换两者位置
        if(arr[max]>arr[index]){
            //交换两者索引处元素位置
            swap(arr,max,index);
            //能力强的下属替换能力不行的领导，还需要考察这个能力不行的领导是否符合原本下属的位置
            max_heap_adjust(arr, max, maxIndex); //max代表原本下属的位置(索引)，需要考察下是否满足大根堆条件
        }
    }

    private static void swap(int[] arr, int index1, int index2) {
        int temp= arr[index1];
        arr[index1]=arr[index2];
        arr[index2]=temp;
    }
}
